package gold.digger;

import gold.utils.InputUtil;

import java.util.ArrayList;
import java.util.List;

/**
 * Created by fanzhenyu02 on 2020/6/27.
 * common problem solver template.
 */
public class LC901 {
    public long startExecuteTime = System.currentTimeMillis();


    class StockSpanner {
        List<Integer> dp;
        List<Integer> num;

        public StockSpanner() {
            dp = new ArrayList<>();
            num = new ArrayList<>();
        }

        public int next(int price) {
            num.add(price);
            if (num.size() == 1) {
                dp.add(-1);
                return 1;
            }

            if (price < num.get(num.size() - 2)) {
                dp.add(num.size() - 2);
                return 1;
            }

            int biggerIdx = dp.get(dp.size() - 1);
            while (biggerIdx != -1 && price >= num.get(biggerIdx)) {
                biggerIdx = dp.get(biggerIdx);
            }

            dp.add(biggerIdx);
            return dp.size() - biggerIdx - 1;
        }
    }

    public void run() {
        StockSpanner solution = new StockSpanner();
        int[] arr = InputUtil.toIntegerArray("[28,14,28,35,46,53,66,80,87,88]");
//        int[] arr = InputUtil.toIntegerArray("[100, 80, 60, 70, 60, 75, 85]");
//        int[] arr = InputUtil.toIntegerArray("[90,21,21,68,94,13,1,37,3,61,86,19,12,35,96]");
        for (int stock : arr) {
            System.out.println(solution.next(stock));
        }
    }

    public static void main(String[] args) throws Exception {
        LC901 an = new LC901();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
